package 打家劫舍III;

/**
 * @author: AirMan
 * @date: 2025/5/13 11:54
 * @description:
 */
public class Solution3 {
    public int rob(TreeNode root) {
        // 递推和记忆化递归方法 对于偷与不偷得到的最大金钱都没有做记录，而是需要实时计算
        // ① dp数组及其含义：dp[0]代表不选择该节点的最大金额，dp[1]代表选择该节点的最大金额
        // ② 状态转移方程：后序遍历的过程中，接受子树的dp数组，然后选择当前的选择状态
        //    dp[0] = Math.max(leftDp[0], leftDp[1]) + Math.max(rightDp[0], rightDp[1]);
        //    dp[1] = leftDp[0] + rightDp[0];
        // ③ dp数组的初始化：if root == null return new int[2]{0, 0};
        // ④ 遍历顺序：从底部向上进行遍历

        int[] result = dynamicProgrammingAndRecursion(root);
        return Math.max(result[0], result[1]);
    }

    private int[] dynamicProgrammingAndRecursion(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }
        // left
        int[] leftDp = dynamicProgrammingAndRecursion(root.left);
        // right
        int[] rightDp = dynamicProgrammingAndRecursion(root.right);
        int[] dp = new int[2];
        // 不选择当前根节点，那么左右子树可以选择偷或者不偷
        dp[0] = Math.max(leftDp[0], leftDp[1]) + Math.max(rightDp[0], rightDp[1]);
        // 选择当前根节点
        dp[1] = root.val + leftDp[0] + rightDp[0];
        return dp;
    }
}
